package 纯数组;

public class NC101缺失数字 {

    /**
     * 从0,1,2,...,n这n+1个数中选择n个数，组成有序数组，请找出缺失的那个数，要求O(n)尽可能小。
     * 示例1
     * 输入
     * [0,1,2,3,4,5,7]
     * 返回值
     * 6
     */

    public int solve (int[] a) {

        if(a.length<1){
            return 0;
        }

        int left=0;
        int right=a.length-1;
        int mid;

        while (left<=right){
            mid=(right-left)/2+left;
            if(mid==0&&a[mid]!=0){
                return 0;
            }
            if(mid==a.length-1){
                return a.length;
            }
            if(a[mid-1]+1<a[mid]){
                return mid;
            }
            if(a[mid+1]-1>a[mid]){
                return mid+1;
            }
            if(a[mid]==mid){
                //在右边
                left=mid+1;
            }else{
                //在左边
                right=mid-1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        NC101缺失数字 n=new NC101缺失数字();
        int[] arr={0,1,2,3,4,5,6,7,8};
        int result = n.solve(arr);
        System.out.println(result);
    }

}
